Kirby's Adventure and Kirby Super Star compression format.
by Parasyte, 2004


I Have attempted to explain the compression format to the best of my
ability. This document may be confusing, even to an experienced hacker. The
compression format used is one of the most expansive I've seen. It uses seven
different kinds of compression techniques, which includes the common LZ-Copy,
RLE, and uncompressed data methods. The remaining types are simply variations
of LZ-Copy and RLE.

The decompressor begins by reading a control byte from the source.
(Source = compressed data) The upper three bits of the control byte are checked
to determine the compression type. Compression types are in the range 0 - 6.
The "8th compression type" is an expansion of the previous 7 types. It provides
the compression type with a greater length attribute than normally available.


The control byte format is as follows:

(binary) tttxxxxx
t: Compression type.
x: See below.


Lower 5 bits of control byte:
For compression types 0-6 are as follows:

(binary) lllll
l: Length attribute.


For "compression type 7" (expansion) are as follows:

(binary) tttll
t: Expanded compression type. (Actual compression type to use)
l: Upper two bits of length attribute.



For compression types 0-6, the byte(s) following the control byte is the
data used for output. Maximum length: 32.
For compression type 7 (expansion), the byte following the control byte is the
lower 8 bits of the length attribute. The byte(s) following the length is the
data used for output. Maximum length: 1024.
In both cases, (length) is incremented; making a length of zero output 1 byte.


Compression types:

0: Uncompressed copy
Copies (length) number of (data) bytes to output.
1: Run-Length Encoding (RLE)
Copies 1 byte of (data) to output (length) times.
2: 2-Byte RLE
Copies 2 bytes of (data) in sequence to output (length) times.
3: RLE++
Copies 1 byte of (data) to output (length) times, incrementing (data) after
each byte output.
4: LZ-Copy
Uses (data) as an offset into the output. Copies from offset (length) times.
5: Bit-reversing LZ-Copy
Uses (data) as an offset into the output. Copies from offset (length) times,
reversing the bits of every byte copied. (NOT Xor 255)
6: LZ-Reverse-Copy
Uses (data) as an offset into the output. Copies from offset (length) times,
moving backward from offset.
7: Invalid compression type
This compression type can only appear if it has been extended first. In this
case, it assumes the compression type of 4; LZ-Copy.


Examples:
$03,$94,$24,$51,$73
Control Byte: $03 (000,00011)
Compression Type: 0
Length Attribute: 4
Data: $94,$24,$51,$73
Action: $94,$24,$51,$73 written to output.

$24,$65
Control Byte: $24 (001,00100)
Compression Type: 1
Length Attribute: 5
Data: $65
Action: $65,$65,$65,$65,$65 written to output.

$42,$81,$91
Control Byte: $42 (010,00010)
Compression Type: 2
Length Attribute: 3
Data: $81,$91
Action: $81,$91,$81,$91,$81,$91 written to output.

$65,$50
Control Byte: $65 (011,00101)
Compression Type: 3
Length Attribute: 6
Data: $50
Action: $50,$51,$52,$53,$54,$55 written to output.

$83,$00,$05
Control Byte: $83 (100,00011)
Compression Type: 4
Length Attribute: 4
Data: $00,$05
Action: Four bytes from [(beginning of output)+$0005] copied to
output.

$B0,$01,$43
Control Byte: $A7 (101,10000)
Compression Type: 5
Length Attribute: 17
Data: $01,$43
Action: Seventeen bytes from (beginning of output)+$0143
copied to output and bit-reversed.

$C4,$00,$10
Control Byte: $C4 (110,00100)
Compression Type: 6
Length Attribute: 5
Data: $00,$10
Action: Five bytes from (beginning of output)+$0010 copied to
output, bytes read backward.

$E8,$3F,$00
Control Byte: $E8 (111,010,00)
Compression Type: 2 (Expanded)
Length Attribute: 64
Data: $00
Action: Sixty-four bytes of '$00' written to output.
